package algorithms.a04heap;

import algorithms.utis.AlgorithmsUtis;
import algorithms.utis.SortTestHelper;
import org.apache.commons.lang3.RandomUtils;

import java.util.Arrays;

/**
 * 索引堆排序
 *
 * @author 王昊然
 * @create 2018-02-09 8:55
 **/
public class IndexMaxHeapSort {

    public static void sort(Comparable[] arr) {

        int n = arr.length;

        IndexMaxHeap<Comparable> indexMaxHeap = new IndexMaxHeap<Comparable>(n);

        for( int i = 0 ; i < n ; i++ )
            indexMaxHeap.insert(i, arr[i]);

        for( int i = n-1 ; i >= 0 ; i -- )
            arr[i] = indexMaxHeap.extractMax();
    }

    public static void main(String[] args) {
        int N = 15000;
        Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 200000);
        SortTestHelper.testSort(IndexMaxHeapSort.class, arr);

        return;
    }
}
